package sort;

import java.util.Random;
import java.util.concurrent.TimeUnit;

public class QuickSort {
    private static final Random RANDOM = new Random();

    public static void main(String[] args) {
        int n = 1000000;
        int attempts = 30;
        int average = 0;
        for (int j = 10; j < attempts; j++) {
            int[] a = new int[n];
            Random random = new Random();
            for (int i = 0; i < n; i++) a[i] = random.nextInt(100);

            // System.out.println("Initial array: " + Arrays.toString(a));
            long start = System.nanoTime();
            sort(a);
            long end = System.nanoTime();
            average += (end - start);
            //System.out.println("Sorted  array: " + Arrays.toString(a));
            //System.out.println();
            System.out.println(j + ") sort.Sorting time: " + TimeUnit.NANOSECONDS.toMillis(end - start) + "ms.");
        }
        System.out.println();
        System.out.println("Average: " + TimeUnit.NANOSECONDS.toMillis(average / (attempts - 9)) + "ms");
    }

    private static void sort(int[] a) {
        if (a == null || a.length <= 1) return;
        quickSort(a, 0, a.length - 1);
    }

    public static int binarySearch(int[] a, int value) {
        if (a == null) return -1;
        int left = 0, right = a.length - 1;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (a[middle] > value) {
                right = middle - 1;
            } else {
                if (a[middle] < value) left = middle + 1;
                else return middle;
            }
        }
        return -1;
    }

    public static void quickSort(int[] a, int l, int r) {
        int left = l, right = r;
        int pivot = a[left + RANDOM.nextInt(right - left)];
        //int pivot = a[left];
        while (left <= right) {
            while (a[left] < pivot) left++;
            while (a[right] > pivot) right--;
            if (left <= right) swap(a, left++, right--);
        }
        if (l < right) quickSort(a, l, right);
        if (r > left) quickSort(a, left, r);
    }

    private static void swap(int[] a, int l, int r) {
        int temp = a[l];
        a[l] = a[r];
        a[r] = temp;
    }
}
